package com.mystudy.leetcode.problem.sort.p_75;

import org.junit.After;
import org.junit.Before;
import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * @program: infoalgorithm
 * @description: 颜色分类
 * @author: zhouzhilong
 * @create: 2019-08-02 16:39
 **/

/**
 * 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
 * <p>
 * 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
 * <p>
 * 注意:
 * 不能使用代码库中的排序函数来解决这道题。
 * <p>
 * 示例:
 * <p>
 * 输入: [2,0,2,1,1,0]
 * 输出: [0,0,1,1,2,2]
 * 进阶：
 * <p>
 * 一个直观的解决方案是使用计数排序的两趟扫描算法。
 * 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
 * 你能想出一个仅使用常数空间的一趟扫描算法吗？
 */
public class Solution {
    private static final Logger LOGGER = LoggerFactory.getLogger(Solution.class);

    long startTime = 0L;
    long endTime = 0L;


    @Before
    public void before() {
        startTime = System.nanoTime();
    }


    @After
    public void after() {
        endTime = System.nanoTime();
        double cost = (endTime - startTime) / 1000.0;
        LOGGER.debug("cost = [{} us ]",cost);
    }


    @Test
    public void test() {
        sortColors(new int[]{2,0,2,1,1,0});

    }

    public void sortColors(int[] nums) {
        int redCount = 0;
        int whiteCount = 0;
        int blueCount = 0;

        for (int num : nums) {
            switch (num) {
                case 0:
                    redCount++;
                    break;
                case 1:
                    whiteCount++;
                    break;
                case 2:
                    blueCount++;
                    break;
            }
        }
        int count = 0;
        while(redCount>0){
            nums[count] = 0;
            redCount--;
            count++;
        }

        while(whiteCount>0){
            nums[count] = 1;
            whiteCount--;
            count++;
        }
        while(blueCount>0){
            nums[count] = 2;
            blueCount--;
            count++;
        }
        LOGGER.debug("nums = [{}]",nums);
    }


}
